package com.atguigu.linkedlist;

import javax.lang.model.element.VariableElement;
import java.util.Stack;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "公孙胜", "入云龙");
        HeroNode hero5 = new HeroNode(5, "关胜", "大刀");
        HeroNode hero6 = new HeroNode(6, "林冲", "豹子头");
        HeroNode hero7 = new HeroNode(7, "秦明", "霹雳火");

        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero4);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);

//        singleLinkedList.list();



//        System.out.println("打印反转...");
//        singleLinkedList.printReverse();

//        System.out.println("翻转...");
//
//        SingleLinkedList reverseList = singleLinkedList.reverseList();
//
//        reverseList.list();



        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero6);

        System.out.println("单链表按序号相加");

        SingleLinkedList list2 = new SingleLinkedList();
        list2.add(hero3);
        list2.add(hero5);
        list2.add(hero7);

        SingleLinkedList resultList = singleLinkedList.addList(list2);
        resultList.list();


        /*
        System.out.println("按照顺序添加...");

        singleLinkedList.list();

        System.out.println("修改节点...");

        HeroNode heroNode22 = new HeroNode(2, "卢本伟", "五五开");
        singleLinkedList.update(heroNode22);

        singleLinkedList.list();

        System.out.println("删除节点...");
        singleLinkedList.remove(1);
        singleLinkedList.remove(4);
        singleLinkedList.list();

        System.out.printf("size=%d",singleLinkedList.size());

        System.out.println("获取倒数第k个节点...");

        int lastIndex=3;
        HeroNode last = singleLinkedList.getLast(lastIndex);
        System.out.printf("倒数第%d个节点是%s",lastIndex,last);

        System.out.println("翻转链表...");
        SingleLinkedList reverse = singleLinkedList.reverse();
        reverse.list();*/

    }
}

class SingleLinkedList implements LinkedList{
    HeroNode head=new HeroNode(0,"","");

    public void add(HeroNode heroNode){
        HeroNode temp=head;
        while(true){
            if (temp.next!=null) {
                temp=temp.next;
            }else{
                temp.next=heroNode;
                break;
            }
        }
    }

    /**
     * 按照数据增加节点.
     * 正向从第一个开始遍历.
     * 当获取某个节点的no第一次小于参数节点, 则参数节点应该插在上一个节点和这个节点之间.
     * 为了能够快捷的获取的上个节点, 故temp使用上个节点来替代.
     * @param heroNode
     */
    public void addByOrder(HeroNode heroNode){
        HeroNode temp=head;

        // 表示参数节点是否在某个节点之前
//        boolean flag=false;
        while(true){
            if (temp.next==null) {
                temp.next=heroNode;
                return;
            }
            if (temp.next.no==heroNode.no) {
                System.out.printf("序号为%d的节点已存在,无法插入",heroNode.no);
                return;
            }
            if(temp.next.no>heroNode.no){
                heroNode.next=temp.next;
                temp.next=heroNode;
                return;
            }
            temp=temp.next;
        }
    }

    // 会破坏原来的节点结构
    public SingleLinkedList addList(SingleLinkedList list2){
        SingleLinkedList resultList = new SingleLinkedList();

        HeroNode temp1 = head.next;
        HeroNode temp2 = list2.head.next;
        HeroNode tempResult = resultList.head;

        while(temp1!=null||temp2!=null){
            if (temp1==null||temp2.no<temp1.no) {
                tempResult.next=temp2;
                temp2=temp2.next;
                tempResult=tempResult.next;
                continue;
            }
            if(temp2.no==temp1.no){
                System.out.printf("节点序号%d相同,随机排序",temp2.no);
            }
            tempResult.next=temp1;
            temp1=temp1.next;
            tempResult=tempResult.next;


        }
        tempResult.next=null;
        return resultList;
    }

    /**
     * 更新节点
     * 1. 遍历每个节点,直到发现no匹配的节点
     * 2. 匹配节点内容更新name和nickname
     * 3. 如果一直无法匹配, 则提示更新失败
     */
    public void update(HeroNode node){
        HeroNode temp=head;
        if (temp.next==null) {
            System.out.println("链表为空");
            return;
        }

        while(true){
            if (temp.next==null) {
                System.out.println("未找到匹配的节点");
                return;
            }
            if (temp.next.no==node.no) {
                temp.next.name=node.name;
                temp.next.nickname=node.nickname;
                return;
            }

            temp=temp.next;
        }
    }

    /**
     * 删除节点
     * 遍历节点. 当发现序号与参数相同的节点时, 使该节点的前一个节点的后继直接等于该节点的后一个节点即可.
     * java的垃圾回收机制, 会自动将不用的节点内容清除掉
     * @param no
     */
    @Override
    public void remove(int no){
        HeroNode temp=head;
        if (temp.next==null) {
            System.out.println("联表为空");
            return;
        }

        while(true){
            if (temp.next==null) {
                System.out.println("未找到的匹配序号");
                return;
            }
            if (temp.next.no==no) {
                temp.next=temp.next.next;
                return;
            }

            temp=temp.next;
        }
    }


    @Override
    public int size(){
        HeroNode temp=head.next;
        if(temp==null){
            return 0;
        }
        int size=0;
        while(true){
            size++;
            if (temp.next==null) {
                return size;
            }
            temp=temp.next;
        }
    }

    @Override
    public void list(){
        HeroNode temp=head.next;
        if (temp==null) {
            System.out.println("链表为空");
            return;
        }

        while(true){
            if (temp!=null) {
                System.out.println(temp);
                temp=temp.next;
            }else{
                break;
            }
        }
    }

    @Override
    public void add(LinkedListNode node) {
        add((HeroNode) node);
    }

    @Override
    public void addByOrder(LinkedListNode node) {
        add((HeroNode) node);
    }

    @Override
    public void update(LinkedListNode node) {
        update((HeroNode)node);
    }

    public void printReverse(){
        Stack<HeroNode> stack = new Stack<>();
        HeroNode temp=head.next;
        while(temp!=null){
            stack.push(temp);
            temp=temp.next;
        }
        while(!stack.empty()){
            System.out.println(stack.pop());
        }
    }

    public HeroNode getLast(int lastIndex){
        int size = size();
        if (size==0) {
            System.out.println("链表为空");
            return null;
        }

        if (lastIndex<=0||lastIndex>size) {
            return null;
        }

        int targetIndex=size-lastIndex+1;
        HeroNode temp=head.next;
        int i=0;
        while(true){
            i++;
            if (i==targetIndex) {
                return temp;
            }
            // 不可能找不到
            if (temp.next==null) {
                System.out.println("不可能找不到啊...");
                return null;
            }
            temp=temp.next;
        }

    }

    /**
     * 单链表的反转
     * 1. 节点创建一个新的字段. 叫做previous, 仅在反转时临时使用(这个步骤也可以使用创建新类来替代)
     * 2. 正向遍历, 每次遍历都将previous记录下来
     * 3. 遍历到最后, 获取到最后一个节点
     * 4. 从最后一个节点开始, 将previous逆转为next
     * @return
     */
    public SingleLinkedList reverse(){
        HeroNode temp=head.next;
        if (temp==null) {
            return this;
        }
        while(true){
            if (temp.next==null) {
                break;
            }
            temp.next.prev=temp;

            temp=temp.next;
        }
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        while(true){
            // 为了避免影响到原来的链表, 新节点最好要是克隆的.
            singleLinkedList.add(new HeroNode(temp.no,temp.name,temp.nickname));
            if (temp.prev==null) {
                break;
            }

            temp=temp.prev;
        }


        return singleLinkedList;
    }

    /**
     * 按照老师那样翻转
     * @return
     */
    public SingleLinkedList reverseList(){
        HeroNode temp = head.next;
        if (temp==null||temp.next==null) {
            return this;
        }

        SingleLinkedList singleLinkedList = new SingleLinkedList();
        // 这种方式会破坏原来的node集合.如果想要不破坏原来的集合,就必须克隆单个节点
        while(temp!=null){
            HeroNode next=temp.next;
            singleLinkedList.unshift(temp);
            temp=next;
        }

        return singleLinkedList;
    }

    public void unshift(HeroNode node){
        node.next=head.next;
        head.next=node;
    }
}

class HeroNode implements LinkedListNode{
    int no;
    String name;
    String nickname;
    HeroNode next;
    HeroNode prev;

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }




    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}
